from collections import deque


class Solution:
    def nearestExit(self, maze: list[list[str]], entrance: list[int]) -> int:
        m, n = len(maze), len(maze[0])

        def is_exit(r: int, c: int) -> bool:
            if r == entrance[0] and c == entrance[1]:
                return False
            if r == 0 or r == m - 1 or c == 0 or c == n - 1:
                return True
            else:
                return False

        #
        step = 0
        pt = deque([(entrance[0], entrance[1])])
        visited: set[(int, int)] = {(entrance[0], entrance[1])}
        while pt:
            prSize = len(pt)
            for _ in range(prSize):
                # 访问
                x, y = pt.popleft()
                if is_exit(x, y):
                    return step
                # 加节点
                if x - 1 >= 0 and maze[x - 1][y] == '.' and (x - 1, y) not in visited:
                    pt.append((x - 1, y))
                    visited.add((x - 1, y))
                if x + 1 < m and maze[x + 1][y] == '.' and (x + 1, y) not in visited:
                    pt.append((x + 1, y))
                    visited.add((x + 1, y))
                if y - 1 >= 0 and maze[x][y - 1] == '.' and (x, y - 1) not in visited:
                    pt.append((x, y - 1))
                    visited.add((x, y - 1))
                if y + 1 < n and maze[x][y + 1] == '.' and (x, y + 1) not in visited:
                    pt.append((x, y + 1))
                    visited.add((x, y + 1))
            step += 1
        return -1
